//给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。 
//
// 
//
// 示例 1： 
// 
// 
//输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
//输出：[1,2,4,7,5,3,6,8,9]
// 
//
// 示例 2： 
//
// 
//输入：mat = [[1,2],[3,4]]
//输出：[1,2,3,4]
// 
//
// 
//
// 提示： 
//
// 
// m == mat.length 
// n == mat[i].length 
// 1 <= m, n <= 10⁴ 
// 1 <= m * n <= 10⁴ 
// -10⁵ <= mat[i][j] <= 10⁵ 
// 
//
// Related Topics 数组 矩阵 模拟 👍 526 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-08-25 10:26:29
 * @description 498.对角线遍历
 
 */
 
public class DiagonalTraverse {
    public static void main(String[] args) {
    //测试代码
    DiagonalTraverse fun = new DiagonalTraverse();
    Solution solution= fun.new Solution();
        solution.findDiagonalOrder(new int[][]{{1,2,3},{4,5,6},{7,8,9}});
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        // 往右上是 (i-1,j+1)
        // 往左下是 (i+1,j-1)
    public int[] findDiagonalOrder(int[][] mat) {
        boolean reverse=true;
        int m=mat.length;
        int n=mat[0].length;
        int[] ans=new int[m*n];
        int i=0,j=0,idx=0;
        while (idx<m*n){
            if(reverse){
                //右上
                while (i >= 0 && j < n) {
                    ans[idx++] = mat[i][j];
                    i--;
                    j++;
                }
                //处理在上半部分超界的情况
                if (j < n) {
                    i = 0;
                    //处理在右边界超界的情况
                } else {
                    i += 2;
                    j = n - 1;
                }
            }else{
                //左下
                while (i < m && j >= 0) {
                    ans[idx++] = mat[i][j];
                    i++;
                    j--;
                }
                //处理在左边界超界的情况
                if (i < m) {
                    j = 0;
                } else {
                    // 处理在下边界超界的情况
                    i = m - 1;
                    j += 2;
                }
            }
            reverse=!reverse;
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
